package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-07
 */

import java.util.HashMap;

/**
 * 大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
 *
 * 你可以搭配 任意 两道餐品做一顿大餐。
 *
 * 给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。
 *
 * 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
 */
public class leetcode1711 {
    public int countPairs(int[] deliciousness) {
        final int MOD = 1000000007;
        int maxVal = 0;
        for (int val : deliciousness) {
            maxVal = Math.max(maxVal,val);
        }
        //数组中任意两个数的和都不会超过maxSum，因maxSum=数组中的最大数*2
        int maxSum = maxVal*2;
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < deliciousness.length; i++) {
            int val = deliciousness[i];
            //sum表示可能达到的2的幂
            for (int sum = 1; sum <= maxSum; sum<<=1) {
                int count = map.getOrDefault(sum-val,0);
                ans = (ans+count)%MOD;
            }
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        return ans;
    }
}
